home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / machserver / 1.098 / mem / memory.c < prev    next >
C/C++ Source or Header  |  1991-04-21  |  46KB  |  1,607 lines
  1. /*
  2.  *  memory.c --
  3.  *
  4.  *    This file implements a dynamic memory allocation system.
  5.  *    It provides procedures to allocate and release storage,
  6.  *    and also includes monitoring and tracing features.
  7.  *
  8.  * Copyright 1985 Regents of the University of California
  9.  * All rights reserved.
  10.  */
  11.  
  12. #ifndef lint
  13. static char rcsid[] = "$Header: /sprite/src/kernel/mem/RCS/memory.c,v 9.5 90/10/17 11:35:02 rab Exp Locker: mgbaker $ SPRITE (Berkeley)";
  14. #endif /* not lint */
  15.  
  16. #include <stdlib.h>
  17. #include <mem.h>
  18. #include <memInt.h>
  19. #include <sprite.h>
  20. #include <sync.h>
  21. #include <stdio.h>
  22. #undef free
  23.  
  24. /*
  25.  * If the MEM_TRACE flag is defined, extra code will be compiled to allow
  26.  * programs to trace Mem_Alloc and Mem_Free calls.
  27. #define MEM_TRACE
  28.  */
  29.  
  30. /*
  31.  * WARNING: several of the macros in this file expect both integers and
  32.  * pointers to be 32 bits (4 bytes) long.
  33.  */
  34.  
  35. /*
  36.  * This storage allocator consists of two independent allocators,
  37.  * one used for binned objects (<= BIN_SIZE bytes) and the other
  38.  * used for large objects.
  39.  *
  40.  * Both allocators deal with "blocks" of storage, which correspond
  41.  * roughly to the areas that users request and free.  Each block of
  42.  * storage consists of one administrative word followed by the
  43.  * useable area.  All allocations are done in even numbers of words,
  44.  * which means that clients may occasionally get more bytes than
  45.  * they asked for.  Mem_Alloc returns the address of the word just
  46.  * after the administrative word.  The administrative word allows us
  47.  * to keep track of which blocks are in use and which are free, and also
  48.  * keeps track of the sizes of blocks so clients don't have to know how
  49.  * large a block is when they free it.  The low-order bit of the
  50.  * administrative word indicates whether or not the block is free, and
  51.  * the rest of the word tells how large the block is (in bytes
  52.  * including the administrative word).  The next-to-low-order bit
  53.  * of each block is used to indicate that this is a "dummy block"(see
  54.  * the comments for the large-object allocator).  Using the low-order
  55.  * bits for flags works because all blocks that we allocate are always
  56.  * multiples of 4 bytes in length.  There is one exception to this
  57.  * usage of the administrative word, which occurs for free binned objects.
  58.  * In this case the word is a link to the next free binned object instead
  59.  * of a size.  The macros below define the format of the administrative
  60.  * words and how to access them.
  61.  *
  62.  * All objects <= SMALL_SIZE are automatically binned.  In order to bin
  63.  * objects between SMALL_SIZE and BIN_SIZE bytes the routine Mem_Bin
  64.  * should be called.  Note that Mem_Bin must be called before any objects
  65.  * of the size to be binned have been allocated.
  66.  */
  67.  
  68. #ifdef MEM_TRACE
  69.  
  70. typedef struct {
  71.     int        admin;        /* Administrative word. */
  72.     Address    pc;        /* PC of call to Mem_Alloc. */
  73.     int        origSize;    /* Original size given to Mem_Alloc. */
  74.     int         padding;    /* To make it double word aligned */
  75. } AdminInfo;
  76.  
  77. #define GET_ADMIN(blockPtr)    (((AdminInfo *) (blockPtr))->admin)
  78. #define SET_ADMIN(blockPtr, value)  \
  79.             ((AdminInfo *) (blockPtr))->admin = (int) (value)
  80.  
  81. #define GET_PC(blockPtr)    (((AdminInfo *) (blockPtr))->pc)
  82. #define SET_PC(blockPtr)    ((AdminInfo *) (blockPtr))->pc = Mem_CallerPC()
  83.  
  84. #define GET_ORIG_SIZE(blockPtr)    (((AdminInfo *) (blockPtr))->origSize)
  85. #define SET_ORIG_SIZE(blockPtr,size)    \
  86.             ((AdminInfo *) (blockPtr))->origSize = size
  87.  
  88. #else /* MEM_TRACE */
  89. #if defined(sequent)
  90.  
  91. /*
  92.  * Need 16-byte alignment for Sequent Symmetry due to various IO devices
  93.  * (eg, SCED needs 8-byte alignment, DCC needs 16-byte).  Would be nicer if
  94.  * all upper level code doing IO insured the buffers were aligned (hence avoid
  95.  * extra fragmentation here), but will live with this.  Note that this isn't a
  96.  * problem in Sequent Dynix, since all IO buffers are implicitly aligned.
  97.  *
  98.  * Note that can probably align the bin'd objects differently so that the
  99.  * admin word lives just before a 16-byte boundary.  This is more than I want
  100.  * to modify right now ;-)
  101.  *
  102.  * This assumes Vm_RawAlloc() returns 16-byte aligned data, as well.
  103.  */
  104.  
  105. typedef struct {
  106.     int        admin;        /* Administrative word. */
  107.     int         padding[3];    /* To make it 16-byte aligned */
  108. } AdminInfo;
  109.  
  110. #define GET_ADMIN(blockPtr)    (((AdminInfo *) (blockPtr))->admin)
  111. #define SET_ADMIN(blockPtr, value)  \
  112.             ((AdminInfo *) (blockPtr))->admin = (int) (value)
  113. #else   /* sequent */            
  114. typedef double AdminInfo;
  115.  
  116. #define GET_ADMIN(blockPtr)    (*(int *)(AdminInfo *) (blockPtr))
  117. #define SET_ADMIN(blockPtr, value) *((int *)(AdminInfo *) (blockPtr)) = (int) (value)
  118. #endif /* sequent */
  119. #endif /* MEM_TRACE */
  120.  
  121. #define USE_BIT        1
  122. #define DUMMY_BITS    3
  123. #define ADMIN_BITS(admin)    ((admin) & DUMMY_BITS)
  124. #define IS_IN_USE(admin)    ((admin) & USE_BIT)
  125. #define IS_DUMMY(admin)        (((admin) & DUMMY_BITS) == DUMMY_BITS)
  126. #define MARK_DUMMY(admin)    ((admin) | DUMMY_BITS)
  127. #define MARK_IN_USE(admin)    ((admin) | USE_BIT)
  128. #define MARK_FREE(admin)    ((admin) & ~DUMMY_BITS)
  129. #define SIZE(admin)        ((admin) & ~DUMMY_BITS)
  130.  
  131. /*
  132.  * The memory manager is a monitor.  The following definition is
  133.  * for its monitor lock.
  134.  */
  135.  
  136. static Sync_Lock memMonitorLock = Sync_LockInitStatic("memMonitorLock");
  137. #define LOCKPTR (&memMonitorLock)
  138.  
  139. static int mem_NumAllocs = 0;
  140. static int mem_NumFrees = 0;
  141.  
  142. #define    MAX_TO_PRINT    256
  143. static struct {
  144.     int        size;        /* Size of the block. */
  145.     int        num;        /* Number of blocks allocated. */
  146.     int        free;        /* Number of blocks freed. */
  147.     int        inUse;        /* Number of blocks still in use. */
  148.     int        dummy;        /* Number of blocks used as dummy blocks. */
  149. } topN[MAX_TO_PRINT + 1];
  150.  
  151. static void Init _ARGS_((void));
  152.  
  153. #ifdef MEM_TRACE
  154. INTERNAL static void PrintTrace _ARGS_((Boolean allocated,
  155.     register Address infoPtr, Address curPC));
  156. INTERNAL static void DoTrace _ARGS_((Boolean allocated,
  157.     register Address infoPtr, Address curPC, int size));
  158. #endif
  159.  
  160. /*
  161.  * ----------------------------------------------------------------------------
  162.  *
  163.  *    Binned-object allocator: it keeps a separate linked free list
  164.  *    for each size of object less than SMALL_SIZE bytes in size and
  165.  *    a free list for all objects less than BIN_SIZE that have been
  166.  *    specified as being binned by a call to Mem_Bin.
  167.  *    The blocks on each list are linked together via their
  168.  *    administrative words, terminated by a NIL pointer.  Allocation
  169.  *    and freeing are done in a stack-like manner from the front of
  170.  *    the free lists.
  171.  *
  172.  *    Definitions (these are all related:  if you change one, you'll
  173.  *    have to change several):
  174.  *
  175.  *    GRANULARITY: The difference in size between succesive buckets.  This
  176.  *        is determined by data alignment restrictions and should be
  177.  *        a power of 2 to allow for shifting to map from size to bucket.
  178.  *    SIZE_SHIFT: The shift distance to convert between size and bucket.
  179.  *    SMALL_SIZE: largest blocksize (total including administrative word)
  180.  *        managed by default by the binned-object allocator.  This
  181.  *        should be 1 less than a multiple of the granularity.
  182.  *    BIN_SIZE: largest possible that can be binned.  Should be one less
  183.  *        than a multiple of the granularity.
  184.  *
  185.  *    These can be computed from the above constants.
  186.  *
  187.  *    SMALL_BUCKETS: default number of separate free lists.
  188.  *    BIN_BUCKETS: number of binned free lists.
  189.  *    BYTES_TO_BLOCKSIZE: how many bytes a block must contain (total
  190.  *        including admin. word) to satisfy a user request in bytes.
  191.  *    BLOCKSIZE_TO_INDEX: which free list to use for blocks of a given
  192.  *        size (total including administrative word).
  193.  *    INDEX_TO_BLOCKSIZE: the (maximum) size corresponding to a bucket.
  194.  *        This will include the size of the administrative word.
  195.  *
  196.  *    These constants determine how many new blocks are allocated to
  197.  *        a bin at one time.
  198.  *
  199.  *    MIN_BLOCKS_AT_ONCE: The amount allocate the first time, and the amount
  200.  *        to increment the number of blocks each successive time.
  201.  *    MIN_SHIFT: The log2 of MIN_BLOCKS_AT_ONCE.
  202.  *    MAX_BLOCKS_AT_ONCE: the most number of blocks to be allocated at once.
  203.  *
  204.  * ----------------------------------------------------------------------------
  205.  */
  206.  
  207. #if defined(sequent)
  208.  
  209. /*
  210.  * 16 byte alignment to for Sequent Symmetry.  Making granularity also 16
  211.  * bytes has nice cache effects (at least thru Model B; this isn't
  212.  * functionally important, but it may affect performance).
  213.  */
  214. #define GRANULARITY            16
  215. #define SIZE_SHIFT            4
  216.  
  217. /*
  218.  * This SMALL_SIZE determined by examination of memory tracing, 1/89.
  219.  * The BIN_SIZE allows us to bin an FS_BLOCK_SIZE object.
  220.  */
  221. #define SMALL_SIZE            271
  222. #define    BIN_SIZE            4207
  223.  
  224. #else    /* sequent */
  225.  
  226. /*
  227.  * 8 byte granularity to handle SPUR and SPARC.
  228.  */
  229. #define GRANULARITY            8
  230. #define SIZE_SHIFT            3
  231. /*
  232.  * This SMALL_SIZE determined by examination of memory tracing, 1/89.
  233.  * The BIN_SIZE allows us to bin an FS_BLOCK_SIZE object.
  234.  */
  235. #define SMALL_SIZE            271
  236. #define    BIN_SIZE            4199
  237.  
  238. #endif /* sequent */ 
  239.  
  240. #define SMALL_BUCKETS            ((SMALL_SIZE + 1) / GRANULARITY)
  241. #define BIN_BUCKETS            ((BIN_SIZE + 1) / GRANULARITY)
  242. #define MASK                (GRANULARITY - 1)
  243. #define BYTES_TO_BLOCKSIZE(bytes) ((bytes+MASK+sizeof(AdminInfo)) & (~MASK))
  244. #define BLOCKSIZE_TO_INDEX(size)  ((size) >> SIZE_SHIFT)
  245. #define INDEX_TO_BLOCKSIZE(index) ((index) << SIZE_SHIFT)
  246. /*
  247.  * These are set up to allocate 4, 8, 12, and then 16 blocks at a time.
  248.  */
  249. #define MIN_BLOCKS_AT_ONCE        4
  250. #define MIN_SHIFT            2
  251. #define MAX_BLOCKS_AT_ONCE         16
  252.  
  253. /*
  254.  * The following array holds pointers to the first free blocks of each size.
  255.  * Bucket i holds blocks whose total length is INDEX_TO_BLOCKSIZE(i) bytes
  256.  * (including the administrative info).  Blocks from bucket i are used to
  257.  * satisfy user requests ranging from INDEX_TO_BLOCKSIZE(i)-sizeof(AdminInfo)
  258.  * bytes up to INDEX_TO_BLOCKSIZE(i)-1 bytes.
  259.  * Buckets 0 and 1 are never used, since they correspond to blocks too small
  260.  * to hold any information for the user.
  261.  */
  262.  
  263. static Address freeLists[BIN_BUCKETS];
  264.  
  265. /*
  266.  * Used to gather statistics about allocations:
  267.  */
  268.  
  269. static int numBlocks[BIN_BUCKETS];    /* Total number of existing blocks,
  270.                      * both allocated and free, for each
  271.                      * small size.  */
  272. static int numAllocs[BIN_BUCKETS];    /* Total number of allocation requests
  273.                      * made for blocks of each small size.
  274.                      */
  275.  
  276. /*
  277.  * ----------------------------------------------------------------------------
  278.  *    Large-object allocator:  used for blocks that aren't binned.
  279.  *    We expect there to be relatively few allocations
  280.  *    made by the large-object allocator.  Since all the blocks it
  281.  *    allocates are relatively large, fragmentation should be less
  282.  *    than it would be if it allocated small blocks too. All of the
  283.  *    blocks, in use or not, are kept in a single linked list using
  284.  *    their administrative words.  The address of the next block in
  285.  *    the list is found by adding the size of the current block to the
  286.  *    address of its administrative word.  Things are complicated
  287.  *    slightly because the storage area managed by this allocator
  288.  *    may be discontiguous:  there could be several large regions
  289.  *    that it manages, separated by gaps that are managed by some other
  290.  *    storage allocator (e.g. the binned-object allocator).  In this
  291.  *    case, the gaps between regions are handled by making the gaps
  292.  *    look like allocated blocks, with an administrative word at the
  293.  *    end of one region that causes a skip to the beginning of the
  294.  *    next region.  These blocks are called "dummy blocks", and have
  295.  *    special flag bits in their administrative words (see definitions
  296.  *    below).  All the blocks within a region are linked together
  297.  *    in increasing order of address.  However, the different regions
  298.  *    may appear in any order on the list.  Two dummy blocks mark the
  299.  *    beginning and end of the list.
  300.  * ----------------------------------------------------------------------------
  301.  */
  302.  
  303. static char *first, *last;
  304. static char _first[sizeof(AdminInfo) + 4], _last[sizeof(AdminInfo) + 4];
  305.                 /* Dummy blocks marking beginning and
  306.                  * end of free list.  Last has a size of
  307.                  * zero.  */
  308. static Address currentPtr;    /* Next block to consider allocating.
  309.                  * Rotates circularly through free list. */
  310. int largestFree;        /* This holds the size of the largest
  311.                  * free block that's been seen on the
  312.                  * free list.  It's updated as the
  313.                  * list is traversed.  */
  314.  
  315. /*
  316.  * Minimum size of new regions requested by large-object allocator
  317.  * when storage runs out:
  318.  */
  319.  
  320. #define MIN_REGION_SIZE 2048
  321.  
  322. static int numLargeBytes;    /* Total amount of storage managed by
  323.                  * the large allocator.  */
  324. static int numLargeAllocs;    /* Total number of allocation requests
  325.                  * handled by the large allocator.  */
  326. static int numLargeLoops;    /* Number of iterations through the
  327.                  * inner block-checking loop of the
  328.                  * large allocator.  */
  329.  
  330. /*
  331.  * ----------------------------------------------------------------------------
  332.  *    Miscellaneous declarations.
  333.  * ----------------------------------------------------------------------------
  334.  */
  335.  
  336. /*
  337.  * Flag to make sure Init gets called once.
  338.  */
  339.  
  340. static void    Init _ARGS_((void));
  341. static int    initialized = FALSE;
  342.  
  343.  
  344. #ifdef MEM_TRACE
  345.  
  346. /*
  347.  * When Mem_Alloc or Mem_Free is called, a trace record will be printed and/or
  348.  * the number of blocks being used by the caller will be stored in the trace
  349.  * array if the block size is in sizeTraceArray. The array is defined with
  350.  * Mem_SetTraceSizes(). PrintTrace calls a default printing routine; it can
  351.  * be changed with Mem_SetPrintProc().
  352.  */
  353. #define MAX_NUM_TRACE_SIZES    20
  354. #define    MAX_CALLERS_TO_TRACE    20
  355. static    struct TraceElement {
  356.     Mem_TraceInfo    traceInfo;
  357.     struct {
  358.     Address    callerPC;
  359.     int    numBlocks;
  360.     } allocInfo[MAX_CALLERS_TO_TRACE];
  361. } sizeTraceArray[MAX_NUM_TRACE_SIZES];
  362.  
  363. static    int    numSizesToTrace = 0;
  364.  
  365. int        mem_PrintLargeAllocPC = 0;
  366.  
  367. #endif /* MEM_TRACE */
  368.  
  369.  
  370.  
  371. /*
  372.  * ----------------------------------------------------------------------------
  373.  *
  374.  * Init --
  375.  *
  376.  *      Initializes the dynamic storage allocator.
  377.  *
  378.  * Results:
  379.  *      None.
  380.  *
  381.  * Side effects:
  382.  *      The storage allocation structures are initialized.
  383.  *
  384.  * ----------------------------------------------------------------------------
  385.  */
  386.  
  387. INTERNAL static void
  388. Init()
  389. {
  390.     int i;
  391.  
  392.     /*
  393.      * Clear out all of the bins.
  394.      */
  395.     for (i = BIN_BUCKETS - 1; i > SMALL_BUCKETS - 1; i--) {
  396.     numBlocks[i] = -1;
  397.     freeLists[i] = (Address) NIL;
  398.     numAllocs[i] = 0;
  399.     }
  400.  
  401.     /*
  402.      * Clear out the small-object free lists.
  403.      */
  404.     for (; i >= 0; i--) {
  405.     freeLists[i] = (Address) NIL;
  406.     numBlocks[i] = 0;
  407.     numAllocs[i] = 0;
  408.     }
  409.  
  410.     /*
  411.      * Initialize the large-object free list with two dummy blocks that
  412.      * mark its beginning and end. These blocks are declared to be arrays
  413.      * of characters. In order for malloc to work correctly they have to
  414.      * be aligned on word boundaries.
  415.      */
  416. #if 0
  417.     if (((int) first) & 0x3) {
  418.     panic("Mem: 'first' is not word-aligned");
  419.     }
  420.     if (((int) last) & 0x3) {
  421.     panic("Mem: 'last' is not word-aligned");
  422.     }
  423. #else
  424.     first = (char *) (((long)_first + 3) & ~3);
  425.     last = (char *) (((long)_last + 3) & ~3);
  426. #endif
  427.  
  428.     SET_ADMIN(first, MARK_DUMMY(last-first));
  429.     SET_ADMIN(last, MARK_DUMMY(0));
  430.     currentPtr        = first;
  431.     largestFree        = 0;
  432.     numLargeBytes    = 0;
  433.     numLargeAllocs    = 0;
  434.     numLargeLoops    = 0;
  435.  
  436.     MemPrintInit();
  437. }
  438.  
  439. /*
  440.  * ----------------------------------------------------------------------------
  441.  *
  442.  * Mem_Bin --
  443.  *
  444.  *    Make objects of the given size be binned.
  445.  *
  446.  * Results:
  447.  *    None.
  448.  *
  449.  * Side effects:
  450.  *    The bin corresponding to blocks of the given size is initialized.
  451.  *
  452.  * ----------------------------------------------------------------------------
  453.  */
  454. ENTRY void
  455. Mem_Bin(numBytes)
  456.     int    numBytes;
  457. {
  458.     int    index;
  459.  
  460.     LOCK_MONITOR;
  461.  
  462.     if (!initialized) {
  463.         initialized = TRUE;
  464.     Init();
  465.     }
  466.     if (mem_NumAllocs > 0) {
  467.     MemPanic("Mem_Bin: Mem_Alloc already called.\n");
  468.     }
  469.     numBytes = BYTES_TO_BLOCKSIZE(numBytes);
  470.     if (numBytes > BIN_SIZE) {
  471.     UNLOCK_MONITOR;
  472.     return;
  473.     }
  474.     index = BLOCKSIZE_TO_INDEX(numBytes);
  475.     if (numBlocks[index] >= 0) {
  476.     UNLOCK_MONITOR;
  477.     return;
  478.     }
  479.     numBlocks[index] = 0;
  480.  
  481.     UNLOCK_MONITOR;
  482. }
  483.  
  484.  
  485. /*
  486.  * ----------------------------------------------------------------------------
  487.  *
  488.  * malloc --
  489.  *
  490.  *    This procedure allocates a chunk of memory.
  491.  *
  492.  * Results:
  493.  *    The return value is a pointer to an area of at least numBytes
  494.  *    bytes of free storage.  If no memory is available, then this
  495.  *    procedure will never return:  the MemChunkAlloc procedure
  496.  *    determines what will happen.
  497.  *
  498.  * Side effects:
  499.  *    The returned block is marked as allocated and will not be
  500.  *    allocated to anyone else until it is returned with a call
  501.  *    to free().
  502.  *
  503.  * ----------------------------------------------------------------------------
  504.  */
  505.  
  506.  
  507. ENTRY Address
  508. malloc(numBytes)
  509.     register unsigned int numBytes;    /* How many bytes to allocate.
  510.                      *    Must be > 0 */
  511. {
  512.     register int size, admin;
  513.     Address    result;
  514.     Address    newRegion;
  515.     int        regionSize;
  516. #ifdef MEM_TRACE
  517.     int        origSize;
  518. #endif /* MEM_TRACE */
  519.     register int index;
  520.  
  521.     LOCK_MONITOR;
  522.  
  523.  
  524.     mem_NumAllocs++;
  525.  
  526.     if (!initialized) {
  527.         initialized = TRUE;
  528.     Init();
  529.     }
  530.  
  531. #ifdef MEM_TRACE
  532.     origSize = numBytes;
  533. #endif /* MEM_TRACE */
  534.  
  535.     /*
  536.      * Handle binned objects quickly, if possible.
  537.      */
  538.     numBytes = BYTES_TO_BLOCKSIZE(numBytes);
  539.     index = BLOCKSIZE_TO_INDEX(numBytes);
  540.     if (numBytes <= BIN_SIZE && numBlocks[index] != -1) {
  541.     if (freeLists[index] == (Address) NIL) {
  542.         register int blocksAtOnce;
  543.  
  544.         /*
  545.          * There aren't currently any free objects of this size.
  546.          * Call the client's function to obtain another region
  547.          * from the system.  While we're at it, get a whole bunch
  548.          * of objects of this size once and put all but one back
  549.          * on the free list.
  550.          */
  551.         if (numBlocks[index] < MAX_BLOCKS_AT_ONCE) {
  552.         blocksAtOnce = ((numBlocks[index] >> MIN_SHIFT) + 1) *
  553.                 MIN_BLOCKS_AT_ONCE;
  554.         } else {
  555.         blocksAtOnce = MAX_BLOCKS_AT_ONCE;
  556.         }
  557.         regionSize = MemChunkAlloc(blocksAtOnce * numBytes, &newRegion);
  558.  
  559.         while (regionSize >= numBytes) {
  560.         SET_ADMIN(newRegion, freeLists[index]);
  561.         freeLists[index] = newRegion;
  562.         numBlocks[index] += 1;
  563.         newRegion += numBytes;
  564.         regionSize -= numBytes;
  565.         }
  566.  
  567.         /*
  568.          * If we were given more bytes than we wanted, and there aren't
  569.          * quite enough left to make a full block, put the leftovers
  570.          * on the free list for the smallest size.  This may still result
  571.          * in GRANULARITY bytes leftover that we have to throw away.
  572.          */
  573.  
  574.         while (regionSize >= (sizeof(AdminInfo) + GRANULARITY)) {
  575.         SET_ADMIN(newRegion, freeLists[2]);
  576.         freeLists[2] = newRegion;
  577.         numBlocks[2] += 1;
  578.         newRegion += (sizeof(AdminInfo) + GRANULARITY);
  579.         regionSize -= (sizeof(AdminInfo) + GRANULARITY);
  580.         }
  581.     }
  582.  
  583.     result = freeLists[index];
  584.     freeLists[index] = (Address) GET_ADMIN(result);
  585.     SET_ADMIN(result, MARK_IN_USE(numBytes));
  586.     numAllocs[index] += 1;
  587.  
  588. #ifdef MEM_TRACE
  589.     SET_PC(result);
  590.     SET_ORIG_SIZE(result, origSize);
  591.     DoTrace(TRUE, result, (Address)NULL, numBytes);
  592. #endif /* MEM_TRACE */
  593.  
  594.     UNLOCK_MONITOR;
  595.     return(result+sizeof(AdminInfo));
  596.     }
  597.  
  598.     /*
  599.      * This is a large object.  Step circularly through the blocks
  600.      * in the list, looking for one that's large enough to hold
  601.      * what's needed.  Move currentPtr to the next block in the list to
  602.      * make sure that we make forward progress each time Mem_Alloc is called.
  603.      * If we don't then there is an instability in the memory allocator
  604.      * with the following pattern:
  605.      *
  606.      *  while (TRUE) {
  607.      *        addr = malloc(4096);
  608.      *      free(addr);
  609.      *      malloc(248);
  610.      *  }
  611.      *
  612.      * This pattern causes memory to get heavily fragmented.
  613.      */
  614.  
  615.     numLargeAllocs += 1;
  616.     admin = GET_ADMIN(currentPtr);
  617.     currentPtr += SIZE(admin);
  618.     while (TRUE) {
  619.     Address nextPtr;
  620.  
  621.     numLargeLoops += 1;
  622.     admin = GET_ADMIN(currentPtr);
  623.     size = SIZE(admin);
  624.     nextPtr = currentPtr+size;
  625.     if (!IS_IN_USE(admin)) {
  626.     
  627.         /*
  628.          * Several blocks in a row could have been freed since the last
  629.          * time we were here.  If so, merge them together.
  630.          */
  631.  
  632.         while (!IS_IN_USE(GET_ADMIN(nextPtr))) {
  633.         size += SIZE(GET_ADMIN(nextPtr));
  634.         admin = MARK_FREE(size);
  635.         SET_ADMIN(currentPtr, admin);
  636.         nextPtr = currentPtr+size;
  637.         }
  638.         if (size >= numBytes) {
  639.         break;
  640.         }
  641.         if (size > largestFree) {
  642.         largestFree = size;
  643.         }
  644.     }
  645.  
  646.     /*
  647.      * This block won't do the job.  Go on to the next block.
  648.      * If the next block is the end of the list, then go back
  649.      * to the beginning and start again, unless no storage has
  650.      * been freed since the last time we went back.  In this
  651.      * case, allocate a new region of storage.
  652.      */
  653.     
  654.     if (nextPtr != last) {
  655.         currentPtr = nextPtr;
  656.         continue;
  657.     }
  658.  
  659.     if (largestFree > numBytes) {
  660.         largestFree = 0;
  661.         currentPtr = first;
  662.         continue;
  663.     }
  664.  
  665.     if (numBytes < MIN_REGION_SIZE) {
  666.         regionSize = MemChunkAlloc(MIN_REGION_SIZE, &newRegion);
  667.     } else {
  668.         regionSize = MemChunkAlloc(numBytes + sizeof(AdminInfo),
  669.                            &newRegion);
  670.     }
  671.     numLargeBytes += regionSize;
  672.  
  673.     /*
  674.      * If the new region immediately follows the end of the previous
  675.      * region, merge the two together (at this point currentPtr always
  676.      * points to a dummy block whose administrative word points to "last").
  677.      * If we can't merge, then make currentPtr link to the new area.
  678.      */
  679.  
  680.     if (newRegion == (currentPtr+sizeof(AdminInfo))) {
  681.         newRegion = currentPtr;
  682.         regionSize += sizeof(AdminInfo);
  683.     } else {
  684.         SET_ADMIN(currentPtr, MARK_DUMMY(newRegion - currentPtr));
  685.     }
  686.  
  687.     /*
  688.      * Create a dummy block at the end of the new region, which links
  689.      * to "last".
  690.      */
  691.     
  692.     SET_ADMIN(newRegion, MARK_FREE(regionSize - sizeof(AdminInfo)));
  693.     newRegion += regionSize - sizeof(AdminInfo);
  694.     SET_ADMIN(newRegion, MARK_DUMMY(last - newRegion));
  695.  
  696.     /*
  697.      * Continue scanning the list (try currentPtr again in case it
  698.      * merged with the new region).
  699.      */
  700.     }
  701.  
  702.     /*
  703.      * At this point we've got a block that's large enough.  If it's
  704.      * larger than needed for the object, put the rest back on the
  705.      * free list (note: even if the remnant is smaller than the smallest
  706.      * large object, which means it'll be used by itself, we put it back
  707.      * on the list so it can merge with either this block or the next,
  708.      * whichever gets freed first).
  709.      */
  710.     
  711.     if (size == numBytes) {
  712.     SET_ADMIN(currentPtr, MARK_IN_USE(admin));
  713.     } else {
  714.     SET_ADMIN(currentPtr+numBytes, MARK_FREE(size-numBytes));
  715.     SET_ADMIN(currentPtr, MARK_IN_USE(numBytes));
  716.     }
  717.  
  718. #ifdef MEM_TRACE
  719.     SET_PC(currentPtr);
  720.     SET_ORIG_SIZE(currentPtr, origSize);
  721.     DoTrace(TRUE, currentPtr, (Address)NULL, numBytes);
  722. #endif /* MEM_TRACE */
  723.  
  724.     result = currentPtr;
  725.     UNLOCK_MONITOR;
  726.     return(result+sizeof(AdminInfo));
  727. }
  728.  
  729.  
  730. /*
  731.  * ----------------------------------------------------------------------------
  732.  *
  733.  * _free --
  734.  *
  735.  *      Return a previously-allocated block of storage to the free pool.
  736.  *
  737.  * Results:
  738.  *      None.
  739.  *
  740.  * Side effects:
  741.  *      The storage pointed to by blockPtr is marked as free and returned
  742.  *    to the free pool.  Nothing in the bytes pointed to by blockPtr is
  743.  *    modified at this time:  no change will occur until at least the
  744.  *    next call to Mem_Alloc.  This means that callers may use the contents
  745.  *    of a block for a short time after free-ing it (e.g. to read a
  746.  *    "next" pointer).
  747.  *
  748.  * ----------------------------------------------------------------------------
  749.  */
  750.  
  751. ENTRY int
  752. free(blockPtr) 
  753.     Address blockPtr;
  754. {
  755.     return _free(blockPtr);
  756. }
  757.  
  758. ENTRY int
  759. _free(blockPtr)
  760.     register Address blockPtr;    /* Pointer to storage to be freed.  Must
  761.                  * have been the return value from Mem_Alloc
  762.                  * at some previous time.  */
  763. {
  764.     register int  admin;
  765.     register int  index;
  766.     register int  size;
  767.  
  768.     LOCK_MONITOR;
  769.  
  770.     mem_NumFrees++;
  771.  
  772.     if (!initialized) {
  773.         MemPanic("Mem_Free: allocator not initialized!\n");
  774.     return 0;        /* should never get here */
  775.     }
  776.  
  777.     /*
  778.      *  Make sure that this block bears some resemblance to a
  779.      *  well-formed storage block.
  780.      */
  781.     
  782.     blockPtr -= sizeof(AdminInfo);
  783.     admin = GET_ADMIN(blockPtr);
  784.     if (ADMIN_BITS(admin) != USE_BIT) {
  785.     if (!IS_IN_USE(admin)) {
  786.         if (!memAllowFreeingFree) {
  787.         MemPanic("Mem_Free: storage block already free\n");
  788.         }
  789.     } else {
  790.         MemPanic("Mem_Free: storage block is corrupted\n");
  791.     }
  792.     UNLOCK_MONITOR;
  793.     return 0;            /* (should never get here) */
  794.     }
  795.  
  796.     /* This procedure is easier for large blocks than for small ones.
  797.      * If large, just clear the use bit.  Since this block could merge
  798.      * with its neighbors, we don't really know anymore what's the
  799.      * largest size on the free list, so set largestFree to a very
  800.      * large number.  This guarantees that the allocator will check
  801.      * the whole list again before requesting additional memory.
  802.      */
  803.  
  804.     size = SIZE(admin);
  805.     index = BLOCKSIZE_TO_INDEX(size);
  806.     if (size > BIN_SIZE || numBlocks[index] == -1) {
  807.     SET_ADMIN(blockPtr, MARK_FREE(admin));
  808.     largestFree = numLargeBytes;
  809.     } else {
  810.     /*
  811.      * For small blocks, add the block back onto its free list.
  812.      */
  813.  
  814.     SET_ADMIN(blockPtr, freeLists[index]);
  815.     freeLists[index] = blockPtr;
  816.     }
  817.  
  818. #ifdef MEM_TRACE
  819.     DoTrace(FALSE, blockPtr, Mem_CallerPC(), size);
  820. #endif /* MEM_TRACE */
  821.  
  822.     UNLOCK_MONITOR;
  823.     return 0;
  824. }
  825.  
  826. /*
  827.  * Global variables that can be set to control thresholds for printing
  828.  * statistics.
  829.  */
  830.  
  831. static int mem_SmallMinNum = 1;         /* There must be at least this many
  832.                                          * binned objects of a size before info
  833.                                          * about its size gets printed. */
  834. static int mem_LargeMinNum  = 1;        /* There must be at least this many
  835.                                          * non-binned objects of a size before
  836.                                          * info about the size gets printed. */
  837. static int mem_LargeMaxSize = 10000;    /* Info is printed for non-binned
  838.                                          * objects larger than this regardless
  839.                                          * of how many of them there are. */
  840.  
  841. /*
  842.  * ----------------------------------------------------------------------------
  843.  *
  844.  * Mem_Size --
  845.  *
  846.  *      Return the size of a previously-allocated storage block.
  847.  *
  848.  * Results:
  849.  *      The return value is the size of *blockPtr, in bytes.  This is
  850.  *    the total usable size of the block.  It may be slightly greater
  851.  *    than the size actually requested in the Mem_Alloc, since this
  852.  *    module rounds sizes up to convenient boundaries.
  853.  *
  854.  * Side effects:
  855.  *    None.
  856.  *
  857.  * ----------------------------------------------------------------------------
  858.  */
  859.  
  860. ENTRY int
  861. Mem_Size(blockPtr)
  862.     Address blockPtr;    /* Pointer to storage to be freed.  Must have been the
  863.              * return value from Mem_Alloc at some previous time. */
  864. {
  865.     int admin;
  866.  
  867.     LOCK_MONITOR;
  868.  
  869.     if (!initialized) {
  870.         MemPanic("Mem_Size: allocator not initialized!\n");
  871.     UNLOCK_MONITOR;
  872.     return(0);            /* should never get here */
  873.     }
  874.  
  875.     /*
  876.      *  Make sure that this block bears some resemblance to a
  877.      *  well-formed storage block.
  878.      */
  879.     
  880.     blockPtr -= sizeof(AdminInfo);
  881.     admin = GET_ADMIN(blockPtr);
  882.     if (ADMIN_BITS(admin) != USE_BIT) {
  883.     if (!IS_IN_USE(admin)) {
  884.         MemPanic("Mem_Size: storage block is free\n");
  885.     } else {
  886.         MemPanic("Mem_Size: storage block is corrupted\n");
  887.     }
  888.     UNLOCK_MONITOR;
  889.     return(0);            /* (should never get here) */
  890.     }
  891.  
  892.     UNLOCK_MONITOR;
  893.     return(SIZE(admin) - sizeof(AdminInfo));
  894. }
  895.  
  896.  
  897. /*
  898.  *----------------------------------------------------------------------
  899.  *
  900.  * Mem_PrintStats --
  901.  *
  902.  *    Print out memory statistics with Mem_PrintStatsSubr using the
  903.  *    default printing routine and default sizes.
  904.  *
  905.  *    See Mem_PrintStatsSubrInt for details.
  906.  *
  907.  * Results:
  908.  *    None.
  909.  *
  910.  * Side effects:
  911.  *    None.
  912.  *
  913.  *----------------------------------------------------------------------
  914.  */
  915. ENTRY void
  916. Mem_PrintStats()
  917. {
  918.     LOCK_MONITOR;
  919.  
  920.     Mem_PrintStatsSubrInt(memPrintProc, memPrintData, mem_SmallMinNum,
  921.               mem_LargeMinNum, mem_LargeMaxSize);
  922.  
  923.     UNLOCK_MONITOR;
  924. }
  925.  
  926.  
  927. /*
  928.  *----------------------------------------------------------------------
  929.  *
  930.  * Mem_PrintStatsInt --
  931.  *
  932.  *    Print out memory statistics with Mem_PrintStatsSubr using the
  933.  *    default printing routine and default sizes.  Same as Mem_PrintStats
  934.  *    except that this routine does not grab the monitor lock.  This is
  935.  *    intended to be used to print out memory stats when the operating
  936.  *    system runs out of memory after being called by Mem_Alloc and hence
  937.  *    the monitor is already down.
  938.  *
  939.  *    See Mem_PrintStatsSubrInt for details.
  940.  *
  941.  * Results:
  942.  *    None.
  943.  *
  944.  * Side effects:
  945.  *    None.
  946.  *
  947.  *----------------------------------------------------------------------
  948.  */
  949. void
  950. Mem_PrintStatsInt()
  951. {
  952.     Mem_PrintStatsSubrInt(memPrintProc, memPrintData, mem_SmallMinNum,
  953.               mem_LargeMinNum, mem_LargeMaxSize);
  954. }
  955.  
  956.  
  957. /*
  958.  * ----------------------------------------------------------------------------
  959.  *
  960.  * Mem_PrintStatsSubr --
  961.  *
  962.  *      This procedure prints out statistics about memory allocation
  963.  *    so far.  Grabs monitor lock and calls the unmonitored routine
  964.  *    Mem_PrintStatsSubrInt.
  965.  *
  966.  * Results:
  967.  *      None.
  968.  *
  969.  * Side effects:
  970.  *      None.
  971.  *
  972.  * ----------------------------------------------------------------------------
  973.  */
  974. ENTRY void
  975. Mem_PrintStatsSubr(printProc, clientData, smallMinNum, largeMinNum,
  976.     largeMaxSize)
  977.     void     (*printProc)();    /* Procedure to actually print stuff. */
  978.     ClientData    clientData;    /* Argument to pass to printProc. */
  979.     int        smallMinNum;    /* Minimum number of elements in a bucket
  980.                  * before will print out stats. */
  981.     int        largeMinNum;    /* Minimum number of large objects of a given
  982.                  * size before will print out stats about
  983.                  * the size. */
  984.     int        largeMaxSize;    /* Statistics will be printed about all blocks
  985.                  * over size regardless of how many there are*/
  986. {
  987.     LOCK_MONITOR;
  988.  
  989.     Mem_PrintStatsSubrInt(printProc, clientData, smallMinNum, largeMinNum,
  990.               largeMaxSize);
  991.  
  992.     UNLOCK_MONITOR;
  993. }
  994.  
  995.  
  996. /*
  997.  * ----------------------------------------------------------------------------
  998.  *
  999.  * Mem_PrintConfig --
  1000.  *
  1001.  *      Prints out the exact configuration of the dynamic memory allocator
  1002.  *    using the default printing routine.
  1003.  *
  1004.  * Results:
  1005.  *      None.
  1006.  *
  1007.  * Side effects:
  1008.  *    None.
  1009.  *
  1010.  * ----------------------------------------------------------------------------
  1011.  */
  1012.  
  1013. void
  1014. Mem_PrintConfig()
  1015. {
  1016.     Mem_PrintConfigSubr(memPrintProc, memPrintData);
  1017. }
  1018.  
  1019. /*
  1020.  * ----------------------------------------------------------------------------
  1021.  *
  1022.  * Mem_PrintConfigSubr --
  1023.  *
  1024.  *      Uses a client-supplied procedure to print out the exact
  1025.  *    configuration of the dynamic memory allocator.
  1026.  *
  1027.  * Results:
  1028.  *      None.
  1029.  *
  1030.  * Side effects:
  1031.  *      Stuff gets printed (?) by passing it to printProc.  See the
  1032.  *    documentation in Mem_PrintStatsSubr for the calling sequence to
  1033.  *    printProc.
  1034.  *
  1035.  * ----------------------------------------------------------------------------
  1036.  */
  1037.  
  1038. ENTRY void
  1039. Mem_PrintConfigSubr(printProc, clientData)
  1040.     void (*printProc)();    /* Procedure to actually print stuff. */
  1041.     ClientData clientData;    /* Argument to pass to printProc. */
  1042. {
  1043.     register Address ptr;
  1044. #ifdef VERBOSE
  1045.     int i, j;
  1046. #endif /* VERBOSE */
  1047.  
  1048.     LOCK_MONITOR;
  1049.  
  1050.     if (!initialized) {
  1051.     (*printProc)(clientData, "Allocator not initialized yet.\n");
  1052.     return;
  1053.     }
  1054.  
  1055. #ifdef VERBOSE
  1056.     (*printProc)(clientData, "Small object allocator:\n");
  1057.     for (i = 2; i < BIN_BUCKETS; i++) {
  1058.     if (freeLists[i] == (Address) NIL) {
  1059.         continue;
  1060.     }
  1061.     (*printProc)(clientData, "    %d bytes:", i*GRANULARITY);
  1062.     j = 5;
  1063.     for (ptr = freeLists[i]; ptr != (Address) NIL;
  1064.         ptr = (Address) GET_ADMIN(ptr)) {
  1065.         if (j == 5) {
  1066.         (*printProc)(clientData, "\n    ");
  1067.         j = 0;
  1068.         } else {
  1069.         j += 1;
  1070.         }
  1071.         (*printProc)(clientData, "%12#x", ptr);
  1072.     }
  1073.     (*printProc)(clientData, "\n");
  1074.     }
  1075. #endif /* VERBOSE */
  1076.  
  1077.     (*printProc)(clientData, "Large object allocator:\n");
  1078.  
  1079. #ifdef MEM_TRACE
  1080.     (*printProc)(clientData, "    Location   Orig. Size   State\n");
  1081. #else
  1082.     (*printProc)(clientData, "    Location       Size     State\n");
  1083. #endif /* MEM_TRACE */
  1084.  
  1085.     for (ptr = first + SIZE(GET_ADMIN(first)); ptr != last;
  1086.         ptr += SIZE(GET_ADMIN(ptr))) {
  1087.  
  1088. #ifdef MEM_TRACE
  1089.     (*printProc)(clientData, "%12#x %10d", ptr, GET_ORIG_SIZE(ptr));
  1090.     if (IS_DUMMY(GET_ADMIN(ptr))) {
  1091.         (*printProc)(clientData, "     Dummy\n");
  1092.     } else if (IS_IN_USE(GET_ADMIN(ptr))) {
  1093.         (*printProc)(clientData, "     In use (PC=0x%x)\n", GET_PC(ptr));
  1094. #else
  1095.     (*printProc)(clientData, "%12#x %10d", ptr, SIZE(GET_ADMIN(ptr)));
  1096.     if (IS_DUMMY(GET_ADMIN(ptr))) {
  1097.         (*printProc)(clientData, "     Dummy\n");
  1098.     } else if (IS_IN_USE(GET_ADMIN(ptr))) {
  1099.         (*printProc)(clientData, "     In use\n");
  1100. #endif /* MEM_TRACE */
  1101.     } else {
  1102.         (*printProc)(clientData, "     Free\n");
  1103.     }
  1104.     }
  1105.     UNLOCK_MONITOR;
  1106. }
  1107.  
  1108. /*
  1109.  * ----------------------------------------------------------------------------
  1110.  *
  1111.  * Mem_PrintInUse --
  1112.  *
  1113.  *      Uses a default procedure to print out the blocks in allocator
  1114.  *    that are still in use. The original size and the PC of the
  1115.  *    call to Mem_Alloc are printed.
  1116.  *
  1117.  * Results:
  1118.  *      None.
  1119.  *
  1120.  * Side effects:
  1121.  *      Stuff gets printed (?) by passing it to memPrintProc.  See the
  1122.  *    documentation in Mem_PrintStatsSubr for the calling sequence to
  1123.  *    memPrintProc.
  1124.  *
  1125.  * ----------------------------------------------------------------------------
  1126.  */
  1127.  
  1128. ENTRY void
  1129. Mem_PrintInUse()
  1130. {
  1131. #ifdef MEM_TRACE
  1132.     register Address ptr;
  1133.  
  1134.     LOCK_MONITOR;
  1135.  
  1136.     if (!initialized) {
  1137.     (*memPrintProc)(memPrintData, "Allocator not initialized yet.\n");
  1138.     return;
  1139.     }
  1140.  
  1141.     (*memPrintProc)(memPrintData, "Large objects still in use:\n");
  1142.     (*memPrintProc)(memPrintData, "    Location   Orig. Size   Alloc.PC\n");
  1143.  
  1144.     for (ptr = first + SIZE(GET_ADMIN(first)); ptr != last;
  1145.         ptr += SIZE(GET_ADMIN(ptr))) {
  1146.  
  1147.     if (!IS_DUMMY(GET_ADMIN(ptr)) && IS_IN_USE(GET_ADMIN(ptr))) {
  1148.         (*memPrintProc)(memPrintData,"%12#x %10d %12#x\n",
  1149.         ptr, GET_ORIG_SIZE(ptr), GET_PC(ptr));
  1150.     }
  1151.     }
  1152.     UNLOCK_MONITOR;
  1153. #endif /* MEM_TRACE */
  1154. }
  1155.  
  1156. /*
  1157.  *----------------------------------------------------------------------
  1158.  *
  1159.  * Mem_SetTraceSizes --
  1160.  *
  1161.  *    Defines a list of sizes to trace and causes tracing to start.
  1162.  *    If the numSizes is zero or the array ptr is NULL, tracing is
  1163.  *    turned off.
  1164.  *
  1165.  * Results:
  1166.  *    None.
  1167.  *
  1168.  * Side effects:
  1169.  *    Traces of Mem_Alloc and Mem_Free start or end.
  1170.  *
  1171.  *----------------------------------------------------------------------
  1172.  */
  1173. /*ARGSUSED*/
  1174. ENTRY void
  1175. Mem_SetTraceSizes(numSizes, arrayPtr)
  1176.     int          numSizes;        /* # of elements in arrayPtr */
  1177.     Mem_TraceInfo *arrayPtr;        /* Array of block sizes to trace. */
  1178. {
  1179. #ifdef MEM_TRACE
  1180.     int    i;
  1181.  
  1182.     LOCK_MONITOR;
  1183.  
  1184.     if (numSizes <= 0 || arrayPtr == (Mem_TraceInfo *)NIL ||
  1185.     arrayPtr == (Mem_TraceInfo *)NULL) {
  1186.     if (numSizes == -1) {
  1187.         numSizesToTrace = -1;
  1188.     } else {
  1189.         numSizesToTrace = 0;
  1190.     }
  1191.     UNLOCK_MONITOR;
  1192.     return;
  1193.     }
  1194.  
  1195.     if (numSizes > MAX_NUM_TRACE_SIZES) {
  1196.     numSizes = MAX_NUM_TRACE_SIZES;
  1197.     }
  1198.     numSizesToTrace = numSizes;
  1199.     for (i = 0; i < numSizes; i++) {
  1200.     sizeTraceArray[i].traceInfo = arrayPtr[i];
  1201.     sizeTraceArray[i].traceInfo.flags |= MEM_TRACE_NOT_INIT;
  1202.     }
  1203.     UNLOCK_MONITOR;
  1204.  
  1205. #endif /* MEM_TRACE */
  1206. }
  1207.  
  1208.  
  1209. /*
  1210.  *----------------------------------------------------------------------
  1211.  *
  1212.  * Mem_SetPrintProc --
  1213.  *
  1214.  *    Changes the default printing routines
  1215.  *
  1216.  * Results:
  1217.  *    None.
  1218.  *
  1219.  * Side effects:
  1220.  *    The default printing routine is changed.
  1221.  *
  1222.  *----------------------------------------------------------------------
  1223.  */
  1224.  
  1225. ENTRY void
  1226. Mem_SetPrintProc(proc, data)
  1227.     void    (*proc)();        /* Address of new print routine. */
  1228.     ClientData    data;        /* Data to be passed to proc. */
  1229. {
  1230.     LOCK_MONITOR;
  1231.     if (proc != (void(*)())NIL &&
  1232.         proc != (void(*)()) NULL) {
  1233.     memPrintProc = proc;
  1234.     memPrintData = data;
  1235.     }
  1236.     UNLOCK_MONITOR;
  1237. }
  1238.  
  1239. /*
  1240.  * ----------------------------------------------------------------------------
  1241.  *
  1242.  * Mem_PrintStatsSubrInt --
  1243.  *
  1244.  *      This procedure prints out statistics about memory allocation
  1245.  *    so far.
  1246.  *
  1247.  * Results:
  1248.  *      None.
  1249.  *
  1250.  * Side effects:
  1251.  *      The procedure printProc is called several times to print out
  1252.  *    information.  Its calling sequence is:
  1253.  *
  1254.  *    void
  1255.  *    printProc(clientData, format, arg1, arg2, arg3, arg4, arg5)
  1256.  *        ClientData clientData;
  1257.  *        char *format;
  1258.  *
  1259.  *    This is identical to the calling sequence for the standard I/o
  1260.  *    routine Io_Print.  The first argument is the clientData argument
  1261.  *    passed to this procedure, which need not necessarily be a
  1262.  *    (Io_Stream *).  There will never be more than 5 arguments.
  1263.  *    A typical calling sequence is:
  1264.  *    "Mem_PrintStatsSubr(Io_PrintStream, (ClientData) io_StdOut,
  1265.  *                50, 100, 1000)".
  1266.  *
  1267.  * ----------------------------------------------------------------------------
  1268.  */
  1269. INTERNAL void
  1270. Mem_PrintStatsSubrInt(printProc, clientData, smallMinNum, largeMinNum,
  1271.     largeMaxSize)
  1272.     void     (*printProc)();    /* Procedure to actually print stuff. */
  1273.     ClientData    clientData;    /* Argument to pass to printProc. */
  1274.     int        smallMinNum;    /* Minimum number of elements in a bucket
  1275.                  * before will print out stats. */
  1276.     int        largeMinNum;    /* Minimum number of large objects of a given
  1277.                  * size before will print out stats about
  1278.                  * the size. */
  1279.     int        largeMaxSize;    /* Statistics will be printed about all blocks
  1280.                  * over size regardless of how many there are*/
  1281. {
  1282.     register Address    ptr;
  1283.     register int    i;
  1284.     int        totalBlocks, totalAllocs, totalFree;
  1285.     int        allocBytes = 0;
  1286.     int        freeBytes = 0;
  1287.     Boolean    firstTime = TRUE;
  1288.     Boolean    warnedAboutOverflow;
  1289.  
  1290.     if (!initialized) {
  1291.     (*printProc)(clientData, "Allocator not initialized yet.\n");
  1292.     return;
  1293.     }
  1294.  
  1295.     (*printProc)(clientData, "\nTotal allocs = %d, frees = %d\n\n",
  1296.         mem_NumAllocs, mem_NumFrees);
  1297.  
  1298.     (*printProc)(clientData, "Small object allocator:\n");
  1299.     totalBlocks = totalAllocs = totalFree = 0;
  1300.     for (i = 2; i < BIN_BUCKETS; i++) {
  1301.     int    numFree = 0;
  1302.  
  1303.     if (numBlocks[i] <= 0) {
  1304.         continue;
  1305.     }
  1306.     allocBytes += numBlocks[i] * INDEX_TO_BLOCKSIZE(i);
  1307.     for (ptr = freeLists[i];
  1308.          ptr != (Address) NIL;
  1309.          ptr = (Address) GET_ADMIN(ptr)) {
  1310.  
  1311.         freeBytes += INDEX_TO_BLOCKSIZE(i);
  1312.         numFree += 1;
  1313.     }
  1314.     if (numBlocks[i] >= smallMinNum) {
  1315.         if (firstTime) {
  1316.         (*printProc)(clientData,
  1317.                 "    Size     Total    Allocs    In Use\n");
  1318.         firstTime = FALSE;
  1319.         }
  1320.         (*printProc)(clientData, "%8d%10d%10d%10d\n",
  1321.             INDEX_TO_BLOCKSIZE(i), numBlocks[i],
  1322.             numAllocs[i], numBlocks[i] - numFree);
  1323.     }
  1324.     totalBlocks += numBlocks[i];
  1325.     totalAllocs += numAllocs[i];
  1326.     totalFree += numFree;
  1327.     }
  1328.     (*printProc)(clientData, "   Total%10d%10d%10d\n", totalBlocks,
  1329.         totalAllocs, totalBlocks - totalFree);
  1330.     (*printProc)(clientData, "Bytes allocated = %d, freed = %d\n\n",
  1331.                 allocBytes, freeBytes);
  1332.  
  1333.     /*
  1334.      * Initialize the largest N-sizes buffer.
  1335.      */
  1336.     for (i = 0; i < MAX_TO_PRINT + 1; i++) {
  1337.     topN[i].size = -1;
  1338.     topN[i].free = 0;
  1339.     topN[i].dummy = 0;
  1340.     }
  1341.  
  1342.     warnedAboutOverflow = FALSE;
  1343.     for (ptr = first + SIZE(GET_ADMIN(first));
  1344.      ptr != last;
  1345.      ptr += SIZE(GET_ADMIN(ptr))) {
  1346.  
  1347.     int    admin;
  1348.     int    size;
  1349.     Boolean    found;
  1350.  
  1351.     admin = GET_ADMIN(ptr);
  1352.     if (!IS_DUMMY(admin) && !IS_IN_USE(admin)) {
  1353.         freeBytes += SIZE(admin);
  1354.     }
  1355.  
  1356.     size = SIZE(admin);
  1357. #ifdef MEM_TRACE
  1358.     if (size - GET_ORIG_SIZE(ptr) < 4 &&
  1359.         size - GET_ORIG_SIZE(ptr) >= 0) {
  1360.         size = GET_ORIG_SIZE(ptr);
  1361.     }
  1362. #endif /* MEM_TRACE */
  1363.  
  1364.     found = FALSE;
  1365.     for (i = 0; i < MAX_TO_PRINT; i++) {
  1366.         if (size == topN[i].size) {
  1367.         found = TRUE;
  1368.         topN[i].num++;
  1369.         if (IS_DUMMY(admin)) {
  1370.             topN[i].dummy++;
  1371.         } else if (IS_IN_USE(admin)) {
  1372.             topN[i].inUse++;
  1373.         } else {
  1374.             topN[i].free++;
  1375.         }
  1376.         break;
  1377.         } else if (topN[i].size == -1) {
  1378.         found = TRUE;
  1379.         topN[i].size = size;
  1380.         topN[i].num = 1;
  1381.         if (IS_DUMMY(admin)) {
  1382.             topN[i].dummy = 1;
  1383.         } else if (IS_IN_USE(admin)) {
  1384.             topN[i].inUse = 1;
  1385.         } else {
  1386.             topN[i].free = 1;
  1387.         }
  1388.         break;
  1389.         }
  1390.     }
  1391.  
  1392.     if (!found && !warnedAboutOverflow) {
  1393.         (*printProc)(clientData, "Largest-Size buffer overflow: %d\n",size);
  1394.         warnedAboutOverflow = TRUE;
  1395.     }
  1396.     }
  1397.     (*printProc)(clientData, "Large object allocator:\n");
  1398.     (*printProc)(clientData, "   Total bytes managed: %d\n", numLargeBytes);
  1399.     (*printProc)(clientData, "   Bytes in use:        %d\n",
  1400.                         numLargeBytes - freeBytes);
  1401.     firstTime = TRUE;
  1402.     for (i = 0; topN[i].size != -1; i++) {
  1403.     if ((topN[i].num >= largeMinNum || topN[i].size >= largeMaxSize) &&
  1404.         (topN[i].num != topN[i].dummy)) {
  1405.         if (firstTime) {
  1406.         (*printProc)(clientData, "%10s%10s%10s%10s\n",
  1407. #ifdef MEM_TRACE
  1408.             "Orig. Size", "Num", "Free", "In Use");
  1409. #else
  1410.             "Size", "Num", "Free", "In Use");
  1411. #endif /* MEM_TRACE */
  1412.         firstTime = FALSE;
  1413.         }
  1414.         (*printProc)(clientData, "%10d%10d%10d%10d\n",
  1415.         topN[i].size, topN[i].num, topN[i].free, topN[i].inUse);
  1416.     }
  1417.     }
  1418.     (*printProc)(clientData, "\n");
  1419. }
  1420.  
  1421. /*
  1422.  *----------------------------------------------------------------------
  1423.  *
  1424.  * DoTrace --
  1425.  *
  1426.  *    Print and/or store a trace record.
  1427.  *
  1428.  * Results:
  1429.  *    None.
  1430.  *
  1431.  * Side effects:
  1432.  *    None.
  1433.  *
  1434.  *----------------------------------------------------------------------
  1435.  */
  1436. #ifdef MEM_TRACE
  1437. INTERNAL static void
  1438. DoTrace(allocated, infoPtr, curPC, size)
  1439.     Boolean        allocated;    /* If TRUE, we are called by Mem_Alloc,
  1440.                      * otherwise by Mem_Free. */
  1441.     register Address    infoPtr;    /* Address of admin. info. */
  1442.     Address        curPC;        /* If called by Mem_Free, PC of
  1443.                      * call to Mem_Free, NULL otherwise. */
  1444.     int            size;        /* Size actually allocated. */
  1445. {
  1446.     int                    i, j;
  1447.     int                    origSize;
  1448.     Address                callerPC;
  1449.     register    struct    TraceElement    *trPtr;
  1450.  
  1451.     if (numSizesToTrace == -1) {
  1452.     PrintTrace(allocated, infoPtr, curPC);
  1453.     return;
  1454.     }
  1455.  
  1456.     callerPC = GET_PC(infoPtr);
  1457.  
  1458.     origSize = GET_ORIG_SIZE(infoPtr);
  1459.  
  1460.     for (i = 0, trPtr = sizeTraceArray; i < numSizesToTrace; i++, trPtr++) {
  1461.     if (trPtr->traceInfo.flags & MEM_DONT_USE_ORIG_SIZE) {
  1462.         if (trPtr->traceInfo.size != size) {
  1463.         continue;
  1464.         }
  1465.     } else if (trPtr->traceInfo.size != origSize) {
  1466.         continue;
  1467.     }
  1468.     if (trPtr->traceInfo.flags & MEM_PRINT_TRACE) {
  1469.         PrintTrace(allocated, infoPtr, curPC);
  1470.     }
  1471.     if (trPtr->traceInfo.flags & MEM_STORE_TRACE) {
  1472.         register int slot;
  1473.         if (trPtr->traceInfo.flags & MEM_TRACE_NOT_INIT) {
  1474.         for (j = 0; j < MAX_CALLERS_TO_TRACE; j++) {
  1475.             trPtr->allocInfo[j].numBlocks = 0;
  1476.             trPtr->allocInfo[j].callerPC = 0;
  1477.         }
  1478.         trPtr->traceInfo.flags &= ~MEM_TRACE_NOT_INIT;
  1479.         }
  1480.         slot = -1;
  1481.         for (j = 0; j < MAX_CALLERS_TO_TRACE; j++) {
  1482.         if (trPtr->allocInfo[j].callerPC == callerPC) {
  1483.             if (allocated) {
  1484.             trPtr->allocInfo[j].numBlocks++;
  1485.             } else {
  1486.             trPtr->allocInfo[j].numBlocks--;
  1487.             }
  1488.             return;
  1489.         }
  1490.         if ((trPtr->allocInfo[j].numBlocks == 0) && (slot < 0)) {
  1491.             slot = j;
  1492.         }
  1493.         }
  1494.         if ((slot >= 0) && allocated) {
  1495.         trPtr->allocInfo[slot].callerPC = callerPC;
  1496.         trPtr->allocInfo[slot].numBlocks = 1;
  1497.         }
  1498.     }
  1499.     return;
  1500.     }
  1501.     if (size > BIN_SIZE && mem_PrintLargeAllocPC) {
  1502.     printf("malloc(%d[%d]) from PC 0x%x\n", origSize, size, callerPC);
  1503.     }
  1504. }
  1505. #endif /* MEM_TRACE */
  1506.  
  1507.  
  1508.  
  1509. /*
  1510.  *----------------------------------------------------------------------
  1511.  *
  1512.  * Mem_DumpTrace --
  1513.  *
  1514.  *    Dump the allocation trace records for the given size block.  If
  1515.  *    the size is specified as -1 then all trace records for all size
  1516.  *    blocks are dumped.
  1517.  *
  1518.  * Results:
  1519.  *    None.
  1520.  *
  1521.  * Side effects:
  1522.  *    None.
  1523.  *
  1524.  *----------------------------------------------------------------------
  1525.  */
  1526. /*ARGSUSED*/
  1527. void
  1528. Mem_DumpTrace(blockSize)
  1529.     int    blockSize;
  1530. {
  1531. #ifdef MEM_TRACE
  1532.     register    struct    TraceElement    *trPtr;
  1533.     int                    i, j;
  1534.  
  1535.     for (i = 0, trPtr = sizeTraceArray; i < numSizesToTrace; i++, trPtr++) {
  1536.     if (trPtr->traceInfo.size != blockSize && blockSize != -1) {
  1537.         continue;
  1538.     }
  1539.     if (!(trPtr->traceInfo.flags & MEM_STORE_TRACE) ||
  1540.         (trPtr->traceInfo.flags & MEM_TRACE_NOT_INIT)) {
  1541.         continue;
  1542.     }
  1543.  
  1544.     if (trPtr->traceInfo.flags & MEM_DONT_USE_ORIG_SIZE) {
  1545.         (*memPrintProc)(memPrintData, "Trace for block size = %d:\n",
  1546.                       trPtr->traceInfo.size);
  1547.     } else {
  1548.         (*memPrintProc)(memPrintData, "Trace for size = %d (%d):\n",
  1549.                   trPtr->traceInfo.size,
  1550.                   BYTES_TO_BLOCKSIZE(trPtr->traceInfo.size));
  1551.     }
  1552.     (*memPrintProc)(memPrintData, "Caller-PC      Num-blocks  \n");
  1553.     for (j = 0; j < MAX_CALLERS_TO_TRACE; j++) {
  1554.         if (trPtr->allocInfo[j].numBlocks == 0) {
  1555.         break;
  1556.         }
  1557.         (*memPrintProc)(memPrintData, "%8x         %6d\n",
  1558.                       trPtr->allocInfo[j].callerPC,
  1559.                       trPtr->allocInfo[j].numBlocks);
  1560.     }
  1561.     if  (blockSize != -1) {
  1562.         break;
  1563.     }
  1564.     }
  1565. #endif
  1566. }
  1567.  
  1568.  
  1569.  
  1570. /*
  1571.  *----------------------------------------------------------------------
  1572.  *
  1573.  * PrintTrace --
  1574.  *
  1575.  *    Print out the given trace information about a memory trace record.
  1576.  *
  1577.  * Results:
  1578.  *    None.
  1579.  *
  1580.  * Side effects:
  1581.  *    None.
  1582.  *
  1583.  *----------------------------------------------------------------------
  1584.  */
  1585. #ifdef MEM_TRACE
  1586. INTERNAL static void
  1587. PrintTrace(allocated, infoPtr, curPC)
  1588.     Boolean        allocated;    /* If TRUE, we are called by Mem_Alloc,
  1589.                      * otherwise by Mem_Free. */
  1590.     register Address    infoPtr;    /* Address of admin. info. */
  1591.     Address        curPC;        /* If called by Mem_Free, PC of
  1592.                      * call to Mem_Free, NULL otherwise. */
  1593. {
  1594.     if (allocated) {
  1595.     (*memPrintProc)(memPrintData,
  1596.         "Mem_Alloc: PC=0x%x  addr=0x%x  size=%d\n",
  1597.         GET_PC(infoPtr), infoPtr+sizeof(AdminInfo),
  1598.         GET_ORIG_SIZE(infoPtr));
  1599.     } else {
  1600.     (*memPrintProc)(memPrintData,
  1601.         "Mem_Free:  PC=0x%x  addr=0x%x  size=%d *\n",
  1602.         curPC, infoPtr+sizeof(AdminInfo), GET_ORIG_SIZE(infoPtr));
  1603.     }
  1604. }
  1605. #endif /* MEM_TRACE */
  1606.  
  1607.